package club.xiaojiawei.strings;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/2/22 9:44 PM
 * @question 459. 重复的子字符串
 * @description 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 */
public class RepeatedSubstringPattern459 {

    public static void main(String[] args) {
//        找特点
        String s = "abac";
        boolean result = repeatedSubstringPattern(s);
        System.out.println(result);
    }

    /**
     * 民间-滑动窗口法
     * @param s
     * @return
     */
    public static boolean repeatedSubstringPattern(String s) {
        String str = s + s;
//        如果不允许用index或contains方法则自己实现该方法，或者直接用枚举法
        return str.substring(1, str.length() - 1).contains(s);
//        return (s + s).indexOf(s, 1) != s.length();
    }

    /**
     * 官方-枚举
     * @param s
     * @return
     */
    public static boolean repeatedSubstringPattern2(String s) {
        int n = s.length();
//        i表示重复子串的长度，重复子串长度不可能超过指定字符串长度的一半
        for (int i = 1; i * 2 <= n; ++i) {
//            如果重复子串不能被给定字符串整除说明重复子串的长度不可能为当前i
            if (n % i == 0) {
                boolean match = true;
//                对于任意的i∈[n ′,n)，有 s[i] = s[i-n']
                for (int j = i; j < n; ++j) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }

}
